#!/usr/bin/env python
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年09月15日
版    本：v1.0.0
描    述：
Copyright (C) 2019 All rights reserved.
'''


class Solution(object):
    def get_fib(self, N):
        for i in range(3, N+1):
            self.path[i] = self.path[i-2] + self.path[i-1]

    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """

        if N == 0:
            return 0
        if N == 1 or N == 2:
            return 1
        self.path = [0 for _ in range(0, N+1)]
        self.path[0] = 0
        self.path[1] = 1
        self.path[2] = 1

        self.get_fib(N)

        return self.path[N]
